package com.stefan.sort;

import java.util.Arrays;

public class MergeSort1 {

    public void split(int[] element,int left,int right){
        if (left < right) {
            int mid = (left+right)/2;
            split(element,left,mid);//左边
            split(element,mid+1,right);//右边
            //merge
            merge(element,left,mid,right);
        }

    }

    public void merge(int[] element,int left,int mid,int right) {
        int[] temp = new int[element.length];
        int tp = left; // temp 数组的当前的index
        int lp = left;
        int rp = mid+1;

        while (lp<=mid && rp<=right) {
            if (element[lp] < element[rp]) {
                temp[tp] = element[lp];
                lp++;
                tp++;
            } else {
                temp[tp] = element[rp];
                rp++;
                tp++;
            }
        }

        while (lp<=mid) {
            temp[tp++] = element[lp++];
        }
        while (rp<=right) {
            temp[tp++] = element[rp++];
        }

        for (int i = left; i <= right; i++) {
            element[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] data = {7,3,2,9,4,6,0,5,1,8};
        MergeSort1 mergeSort1 = new MergeSort1();
        mergeSort1.split(data,0, data.length-1);

        System.out.println(Arrays.toString(data));
    }

}
